package tree.treerecursion;

import tree.TreeNode;

/**
 * @Classname : DiameterOfBinaryTree
 * @Description :
 * <a href="https://leetcode.cn/problems/diameter-of-binary-tree/">543. 二叉树的直径</a>
 * @Author : chentianyu
 * @Date 2023/1/3 21:51
 */


public class DiameterOfBinaryTree {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }

    /**
     * 后序遍历实现
     *
     * @param root
     * @return
     */
    private int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int leftMaxDepth = maxDepth(root.left);
        int rightMaxDepth = maxDepth(root.right);
        maxDiameter = Math.max(maxDiameter, leftMaxDepth + rightMaxDepth);
        return 1 + Math.max(leftMaxDepth, rightMaxDepth);
    }
}
